#include <vector>
#include <string>
#include <unordered_map>
#include <iostream>
using namespace std;



class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words)
    {
        int word_size = words[0].size();
        vector<string> s_words;
        for (auto i = s.begin(); i < s.end(); i += word_size)
        {
            s_words.push_back(string(i, i + word_size));
        }

        unordered_map<string, int> hash_w;
        unordered_map<string, int> hash_s;
        for (auto& e : words)
        {
            hash_w[e]++;
        }

        vector<int> ret;
        int total_words = words.size();
        int total_word_s = 0;
        int left = 0;
        int right = 0;
        while (right < s_words.size())
        {
            hash_s[s_words[right]]++;
            if (hash_s[s_words[right]] <= hash_w[s_words[right]])
            {
                total_word_s++;
            }
            else
            {
                while (hash_s[s_words[right]] > hash_w[s_words[right]])
                {
                    hash_s[s_words[left]]--;
                    if (hash_s[s_words[left]] < hash_w[s_words[left]] && hash_w[s_words[left]] != 0)
                    {
                        total_word_s--;
                    }
                    left++;
                }
            }

            if (total_word_s == total_words)
            {
                ret.push_back(left* word_size);
            }
            right++;
        }
        return ret;
    }
};

int main()
{
    string s = "lingmindraboofooowingdingbarrwingmonkeypoundcake";
    vector<string> words = { "fooo","barr","wing","ding","wing" };
    auto ret = Solution().findSubstring(s, words);
    for (auto e : ret)
    {
        cout << e << ' ';
    }
    return 0;
}